package com.LeeCode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 完全二叉树插入器
 */

public class Code919 {
    public static void main(String[] args) {
        TreeNode node = new TreeNode(1, new TreeNode(2), null);
        CBTInserter cbtInserter = new Code919().new CBTInserter(node);
        System.out.println(cbtInserter.insert(3));
        System.out.println(cbtInserter.insert(4));
        System.out.println(cbtInserter.get_root().val);
    }

    class CBTInserter {

        Deque<TreeNode> candidate;
        TreeNode root;

        public CBTInserter(TreeNode root) {
            this.candidate = new LinkedList<>();
            this.root = root;

            Deque<TreeNode> queue = new LinkedList<>();
            queue.offer(root);

            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (node.left == null || node.right == null) {
                    candidate.offer(node);
                }
            }
        }

        public int insert(int val) {
            TreeNode child = new TreeNode(val);
            TreeNode node = candidate.peek();
            int ret = node.val;
            if (node.left == null) {
                node.left = child;
            } else {
                node.right = child;
                candidate.poll();
            }
            candidate.offer(child);
            return ret;
        }

        public TreeNode get_root() {
            return root;
        }
    }
}
